The present invention relates generally to a geometry processing system, and more particularly to a three-dimensional geometry processing system in which a surface/surface intersection curve, a surface/curve intersection point, an intersection point between three surfaces and a parameter of a projective point on a surface are generated. This system is applicable to three-dimensional Boolean operations devices, three-dimensional free-form surface processing and others.
In computer aided design, several geometry processing techniques are known and used. Among such conventional techniques in the art are: generating a convex hull of a control point of a free-form surface or curve, generating an intersection point between a free-form surface and a parametric curve, generating an internal intersection point between two free-form surfaces, generating coordinates of points on a free-form surface or curve, generating a normal vector of a free-form surface, generating a derivative vector of a free-form surface or curve, generating an approximate polyhedron based on free-form surface data, generating a polyline (plural line segments) based on free-form surface data, generating an intersection point between a plane and a straight line, generating a projective point by projection from a point onto an algebraic surface or plane, generating an intersection point between three planes, generating a parameter of a free-form surface at a point thereon located at the least distance from a specified point. Some of the above mentioned techniques are applied for carrying out the present invention.
In the prior art, "Surface/Surface Intersection" by R. E. Barnhill, G. Farin, M. Jordan and B. R. Piper in Computer Aided Geometric Design, 1987, vol. 4, No. 1-3, pp. 3-16 and "A Marching Method For Parametric Surface/Surface Intersection" by R. E. Barnhill, S. N. Kersey in Computer Aided Geometric Design, 1990, vol. 7, No. 1, pp. 257-280, disclose that tracing vectors, tracing end conditions and an intersection point between intersection curves are used in free-form surface/surface intersection calculations, but there is no more disclosure about other techniques. "Predictor-Corrector Type of Intersection Algorithm for C.sup.2 Parametric Surfaces" by J. J. Chen and T. M. Ozsoy in Computer Aided Geometric Design, 1988, vol. 20, No. 6, pp. 347-352 discloses the uses of tracing vectors and tracing end conditions in free-form surface/surface intersection calculations, but there is no teaching of other more advanced techniques. If the above techniques are simply applied to a known intersection tracing method for generating an intersection curve between free-form surfaces, it is difficult to judge how to start an intersection tracing procedure because a start point at which the procedure is started cannot be easily determined.
There is also a disclosure in the prior art. "Method of Calculating Arbitrary-Order Parametric Curve/Plane Surface Intersection" by Fujisawa and Takamura in the 39th conference of Information Processing Society of Japan, October, pp. 936-937, discloses a technique of calculating intersection between a curve and a plane. "Method of Calculating Arbitrary-Order Parametric Curve/Plane Surface Intersection" by A. G. O'Neill and Takamura in the 39th conference of Information Processing Society of Japan, October, pp. 938-939, discloses a method of calculating an intersection point between a curve and a quadric surface. However, when these conventional techniques are simply applied, it is difficult to realize a technique or system for generating an intersection point between a curve and a surface.
There is also a conventional technique for generating an intersection point between three planes, or generating an intersection point between three low-order algebraic surfaces. However, there is no disclosure of a more advanced technique for generating an intersection point between three surfaces. Moreover, "Analytic Techniques for Geometric Intersection Problems" by V. Chandru and B. S. Kochar in Geometric Modeling, Farin, G.(Ed), SIAM, Philadelphia, 1987, pp. 305-318, discloses a conventional technique for calculating a geometric intersection. This technique is an analytic approach for solving the intersection problems. However, it is difficult to generate a parameter of a free-form surface at a point when the point does not lie on the surface precisely. The procedure of this technique greatly depends on the type of the surface, and it is difficult to perform reliably the procedure when a higher-order surface is processed.